Each node in a BST contains the key and pointers to other nodes.
Hover over a field in the node diagram to learn about its purpose.
The key (or value) is the data stored in the node. It's used to order the tree. All keys in a node's left subtree must be smaller, and all keys in its right subtree must be larger.
The left pointer references another node which is the root of the left subtree. All keys in this subtree are less than the current node's key.
If a node has no left child, this pointer is null.
The right pointer references the root of the right subtree. All keys in this subtree are greater than the current node's key.
If a node has no right child, this pointer is null.
The optional parent pointer references the node's parent in the tree. While not strictly required for a basic BST, it simplifies some algorithms, such as finding a node's successor or predecessor, and can make rotations in balanced trees easier to implement.